package BF_DP;

public class Test2 {
    /*原始递归的方式
    可能性问题 - 给定一个数组 ,玩家AB依次拿去数字 , A和B每次都只能拿最左和最右的问最后谁会获胜.*/
    public static int win1(int[] arr){
        if (arr == null || arr.length == 0){
            return 0;
        }
        return Math.max(f(arr,0,arr.length-1),s(arr,0,arr.length-1));
    }
    //先手函数
    public static int f(int[] arr,int i,int j){
        if (i == j)return arr[i];
        return Math.max(arr[i]+s(arr,i+1,arr.length-1),arr[j]+s(arr,i,j-1));
    }
    //后手函数
    public static int s(int[] arr,int i,int j){
        if (i == j)return 0;
        return Math.min(f(arr,i+1,j),f(arr,i,j-1));
    }
    /*******************************
     * 改动态规划*/
    public static int dp(int[] arr){
        if (arr == null || arr.length ==0){
            return 0;
        }
        int[][] f = new int[arr.length][arr.length];
        int[][] s = new int[arr.length][arr.length];

        for (int i = 0; i < arr.length; i++) {
            f[i][i] = arr[i];
        }
        int row = 0;
        int col =1;
        //对角线开始位置,row行 col列
        while (col < arr.length){
            int i =row;
            int j =col;
            while (i < arr.length && j< arr.length){
                f[i][j] = Math.max(arr[i]+s[i+1][j],arr[j]+s[i][j-1]);
                s[i][j] = Math.max(f[i+1][j],f[i][j-1]);
                i++;
                j++;
            }
            col++;
        }
        return Math.max(f[0][arr.length-1],s[0][arr.length-1]);
    }
}
